#include <vector>
using namespace std;

// 思路： 二分查找
// 1. 初始化左右指针 left 和 right，分别指向数组的起始和结束位置。
// 2. 进入循环，当 left 小于等于 right 时，计算中间位置 mid。
// 3. 比较中间元素 nums[mid] 与目标值 target 的大小关系：
//   - 如果相等，返回 mid 作为目标值的索引。
//  - 如果 nums[mid] 大于 target，说明目标值在左半部分，更新 right 为 mid - 1。
//  - 如果 nums[mid] 小于 target，说明目标值在右半部分，更新 left 为 mid + 1。
//  4. 循环结束后，left 指针将指向目标值应插入的位置，返回 left。
class Solution
{
public:
    int searchInsert(vector<int> &nums, int target)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }
            else if (nums[mid] > target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return left;
    }
};